package leetcode

/*
 * @lc app=leetcode.cn id=1319 lang=golang
 *
 * [1319] 连通网络的操作次数
 */

// @lc code=start

func makeConnected2(n int, connections [][]int) int {
	if len(connections) < n-1 {
		return -1
	}

	edges := make([][]int, n)
	for _, v := range connections {
		a, b := v[0], v[1]
		edges[a] = append(edges[a], b)
		edges[b] = append(edges[b], a)
	}

	seen := make(map[int]struct{}, n)
	var dfs func(int)
	dfs = func(v int) {
		seen[v] = struct{}{}
		for _, e := range edges[v] {
			if _, ok := seen[e]; !ok {
				dfs(e)
			}
		}
	}

	ans := 0
	for i := 0; i < n; i++ {
		if _, ok := seen[i]; !ok {
			dfs(i)
			ans++
		}
	}
	return ans - 1
}

func makeConnected3(n int, connections [][]int) int {
	if len(connections) < n-1 {
		return -1
	}

	edges := make([][]int, n)
	for _, v := range connections {
		a, b := v[0], v[1]
		edges[a] = append(edges[a], b)
		edges[b] = append(edges[b], a)
	}

	seen := make([]bool, n)
	var dfs func(int)
	dfs = func(i int) {
		seen[i] = true
		for _, v := range edges[i] {
			if !seen[v] {
				dfs(v)
			}
		}
	}

	ans := 0
	for i, v := range seen {
		if !v {
			dfs(i)
			ans++
		}
	}
	return ans - 1
}

func makeConnected(n int, connections [][]int) int {
	if len(connections) < n-1 {
		return -1
	}

	u := newUnionFind(n)
	for _, t := range connections {
		u.unite(t[0], t[1])
	}
	return u.numRoot - 1
}

// @lc code=end
